package leetcode.code0895;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

public class FreqStack {

	Map<Integer, Integer> cnts;
	int p;
	List<Stack<Integer>> list;

	public FreqStack() {
		cnts = new HashMap<>();
		list = new ArrayList<>();
		p = 0;
	}

	public void push(int val) {
		int cnt = cnts.getOrDefault(val, 0);
		if (cnt >= list.size()) {
			list.add(new Stack<>());
		}
		if (cnt > p) {
			p++;
		}
		list.get(cnt).add(val);
		cnts.put(val, cnt + 1);
	}

	public int pop() {
		int ans = list.get(p).pop();
		cnts.put(ans, cnts.get(ans) - 1);
		if (list.get(p).size() == 0) {
			p--;
		}
		return ans;
	}
}
